import demo.MySingleList;

/**
 * 链表面试题
 *
 */
public class Test {
    /**
     *力扣->21.合并两个有序链表
     *      1.创建虚拟节点
     *      2.循环判断节点大小情况
     *      3.判断循环结束条件
     *      4.返回虚拟节点.next节点
     */
    public static MySingleList.ListNode mergeTwoLists( MySingleList.ListNode headA,  MySingleList.ListNode headB) {
        MySingleList.ListNode newHead = new  MySingleList.ListNode(-1);
        MySingleList.ListNode tmp = newHead;

        while(headA != null && headB != null) {
            if(headA.val > headB.val) {
                tmp.next = headB;
                headB = headB.next;
                tmp = tmp.next;
            }else {
                tmp.next = headA;
                headA = headA.next;
                tmp = tmp.next;
            }
        }

        if(headA != null) {
            tmp.next =headA;
        }

        if(headB != null) {
            tmp.next =headB;
        }

        return newHead.next;
    }

    public static void main(String[] args) {
        MySingleList mySingleList = new MySingleList();

        mySingleList.addLast(11);
        mySingleList.addLast(22);
        mySingleList.addLast(33);
        mySingleList.addLast(44);
        mySingleList.addLast(55);
        mySingleList.display();

        MySingleList mySingleList2 = new MySingleList();

        mySingleList2.addLast(1);
        mySingleList2.addLast(23);
        mySingleList2.addLast(32);
        mySingleList2.addLast(45);
        mySingleList2.addLast(59);
        mySingleList2.display();

        MySingleList.ListNode ret = mergeTwoLists(mySingleList.head,mySingleList2.head);
        mySingleList.display(ret);
    }
    /**
     * 链表倒数第K个节点
     */
    public static void main3(String[] args) {
        MySingleList mySingleList = new MySingleList();

        mySingleList.addLast(1);
        mySingleList.addLast(2);
        mySingleList.addLast(3);
        mySingleList.addLast(4);
        mySingleList.addLast(5);
        mySingleList.display();

        MySingleList.ListNode ret  = mySingleList.findKthToTail(4);
        System.out.println(ret.val);
    }
    /**
     * 求链表中间节点
     */
    public static void main2(String[] args) {
        MySingleList mySingleList = new MySingleList();

        mySingleList.addLast(1);
        mySingleList.addLast(2);
        mySingleList.addLast(3);
        mySingleList.addLast(4);
        mySingleList.addLast(5);
        mySingleList.display();
        MySingleList.ListNode ret = mySingleList.middleNode();
        System.out.println(ret.val);
    }
    /**
     * 反转链表
     * @param args
     */
    public static void main1(String[] args) {
        MySingleList mySingleList = new MySingleList();
        mySingleList.addLast(1);
        mySingleList.addLast(2);
        mySingleList.addLast(3);
        mySingleList.addLast(4);
        mySingleList.addLast(5);
        mySingleList.display();

        System.out.println("反转: ");
//        mySingleList.reverseList();
//        mySingleList.display();
        //指定位置打印
        MySingleList.ListNode ret = mySingleList.reverseList();
        mySingleList.display(ret);
    }
}
